home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / tsql / doc / tsql.mail / 000100_nls@cse.iitb.ernet.in _Sat May 1 21:48:00 1993.msg < prev    next >
Internet Message Format  |  1996-01-31  |  6KB
  1. Received: from relay2.UU.NET by optima.CS.Arizona.EDU (5.65c/15) via SMTP
  2.     id AA21109; Sat, 1 May 1993 21:48:00 MST
  3. Received: from spool.uu.net (via LOCALHOST.UU.NET) by relay2.UU.NET with SMTP 
  4.     (5.61/UUNET-internet-primary) id AA23076; Sun, 2 May 93 00:48:09 -0400
  5. Received: from sangam.UUCP by spool.uu.net with UUCP/RMAIL
  6.     (queueing-rmail) id 004726.20115; Sun, 2 May 1993 00:47:26 EDT
  7. Received: by sangam.ncst.ernet.in (4.1/SMI-4.1-MHS-7.0)
  8.     id AA11843; Sun, 2 May 93 10:08:15+0530
  9. Received: from kailash.cse.iitb.ernet.in  by iitb.ernet.in
  10.     SENDMAIL Version (4.1/SMI-4.1-MHS-7.0) 
  11.     id AA22512; Sun, 2 May 93 10:00:42+0530
  12. Received: by kailash.cse.iitb.ernet.in (4.1/SMI-4.1)
  13.     id AA03479; Sun, 2 May 93 10:02:07 IST
  14. Date: Sun, 2 May 93 10:02:07 IST
  15. From: nls@cse.iitb.ernet.in (N L Sarda)
  16. Message-Id: <9305020432.AA03479@kailash.cse.iitb.ernet.in>
  17. To: tsql@cs.arizona.edu
  18.  
  19.         BENCHMARK QUERIES : ON THEIR CLASSIFICATION
  20.  
  21. In our efforts to define classes of queries to be used as benchmarks,
  22. I felt that the classification can also be worked out from user's
  23. point of view (in addition to the classification done by CSJensen
  24. based on SQL format) so that certain types, expected to be more
  25. frequent than others, can be emphasized. The following is an 
  26. exploration in this direction.
  27.  
  28. Our target database contains historical data of one/more sets of
  29. entities. An entity has many facts stored about it in the database.
  30. A fact is true over some valid-time interval. There is one 'current'
  31. fact and the others are history (past facts). A real world entity
  32. may be 'in and out' of our database at various times (eg., an
  33. employee being fired and re-hired). Thus, it exists sometimes and
  34. does not at other.
  35.  
  36. Our retrieval may obtain data from one entity set or from multiple
  37. entity sets. A particular case of interest in multiple entity set
  38. query is when the entities existed concurrently. 
  39.  
  40. Our retrieval might ask for full facts stored in database, or parts
  41. of facts with coalesceing and/or time-slicing. Latter limits time values
  42. in result to the time-slice boundaries.
  43.  
  44. The focus of retrieval may be only the current data, only the past
  45. data, or the historical data (current + past). On the other hand, user
  46. may want to obtain aggregated results.
  47.  
  48. The retrieval may be constrained by a predicate on non-temporal as
  49. well as temporal attributes. We may focus only on the latter for
  50. defining taxonomy for our benchmark queries.
  51.  
  52. A large number of time domain operators (or, functions) can be
  53. identified for
  54. constructing temporal predicates. Various query languages may differ
  55. with respect to what operators are included by them. However, since
  56. languages can be easily enriched with more of these operators/functions,
  57. it may not be necessary to define query classes based on these
  58. operators.
  59.  
  60. We now come to formally stating our way of query classes. We use 
  61. COBOL type notation for this : square brackets give an option
  62. and braces define a choice. Words outside brackets/braces are
  63. for readability. (The ugly representation of large braces may please
  64. be pardoned.)
  65.  
  66. ------------------------------------------------------------
  67. A query class is
  68.  
  69.    [CONCURRENT]  [TIME-SLICED]  [COALESCED]
  70.                   
  71.      |  CURRENT      |
  72.      |  PAST         |
  73.      {  HISTORICAL   }      
  74.      |  AGGREGATED   |
  75.      |               |
  76.  
  77. retrieval 
  78. [
  79. based on    
  80.  
  81.      |  EXISTANCE    |
  82.      {               }   of
  83.      | NON-EXISTANCE |
  84.  
  85. [AGGREGATED] relationship
  86.  
  87.      |  IN / WITH  |
  88.      {             }
  89.      |  AT ALL     |
  90.  
  91.          |  INSTANT    |
  92.          {  INTERVAL   }
  93.          |  ELEMENT    |
  94.          |  DURATION   |
  95.  
  96. specified by
  97.  
  98.       |  user             |
  99.       {                   }
  100.       |  computed from    |
  101.       |  other data       |
  102. ]
  103. ----------------------------------------------------------
  104.  
  105. Let us mention below some example classes obtained from above 
  106. categorization of query classes :
  107.  
  108. 1. current retrieval (based on non-temporal predicate)
  109. 2. historical retrieval based on existance relationship in
  110.    (an) interval specified by user.
  111. 3. time-sliced coalesced historical retrieval based on existance
  112.    relationship at all (instants in the) interval given (a) by
  113.    user, and (b) computed (possibly using another retrieval).
  114. 4. concurrent historical retrieval based on existance relationship
  115.    with an interval.
  116. 5. past retrieval based on non-existance relationship at all
  117.    (instants in an) interval given by user.
  118.  
  119.  
  120. The above definition also leads to a fairly large number of query
  121. classes. It may be desirable to cut down the number by not
  122. considering every possible combination.
  123.  
  124. The classification above can be easily related with the taxonomy
  125. proposed by Jensen as follows :
  126. a) concurrent multi-entity retrieval cooresponds to imposed interval
  127.    valid-time component in output and containment-based operator on
  128.    intervals of participating entities (ie., relations) in selection
  129.    based taxonomy. There are many other ways of relating entities
  130.    other than their concurrent existance, but concurrent will be
  131.    more commonly required. The other categories need to be
  132.    explicitely 'programmed' using suitable operators in selection
  133.    and computations in output.
  134. b) time-slicing can also be expressed using interval derivation in
  135.    output and containment operator in selection.
  136. c) there is no easy way of specifying coalescing without complicated
  137.    grouping and computations. The situation is similar to some extent
  138.    with 'distict' in SQL, where duplicates are not aotomatically
  139.    eliminated. We expect that coalescing may also not be done
  140.    automatically in temporal SQLs.
  141. d) queries on current and past data are straightforward to
  142.    express in Jensen taxonomy also, but are mentioned explicitely
  143.    here as a class because of their importance (likely to be
  144.    more frequent).
  145. e) the word 'relationship' in the above class definition format
  146.    represents various possible time domain operators (including
  147.    the duration, ordering and containment based operators
  148.    defined in Jensen taxonomy).
  149. f) the queries based on 'non-existance' are emphasized as they
  150.    are easy to state in English, but difficult to formulate in 
  151.    SQL (usually need nested queries).
  152.  
  153.  
  154. Comments/questions are welcome.
  155.  
  156. Nandlal Sarda
  157.